/*
 * Copyright (C) 2007 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.collect;

import static com.google.common.base.Preconditions.checkState;
import static com.google.common.collect.CollectPreconditions.checkNonnegative;
import static java.util.Objects.requireNonNull;

import com.google.common.annotations.GwtCompatible;
import com.google.common.annotations.GwtIncompatible;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Objects;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import com.google.j2objc.annotations.WeakOuter;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.Arrays;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.NoSuchElementException;
import java.util.Set;
import javax.annotation.CheckForNull;

import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * Implementation of {@code Multimap} that does not allow duplicate key-value entries and that
 * returns collections whose iterators follow the ordering in which the data was added to the
 * multimap.
 *
 * <p>The collections returned by {@code keySet}, {@code keys}, and {@code asMap} iterate through
 * the keys in the order they were first added to the multimap. Similarly, {@code get}, {@code
 * removeAll}, and {@code replaceValues} return collections that iterate through the values in the
 * order they were added. The collections generated by {@code entries} and {@code values} iterate
 * across the key-value mappings in the order they were added to the multimap.
 *
 * <p>The iteration ordering of the collections generated by {@code keySet}, {@code keys}, and
 * {@code asMap} has a few subtleties. As long as the set of keys remains unchanged, adding or
 * removing mappings does not affect the key iteration order. However, if you remove all values
 * associated with a key and then add the key back to the multimap, that key will come last in the
 * key iteration order.
 *
 * <p>The multimap does not store duplicate key-value pairs. Adding a new key-value pair equal to an
 * existing key-value pair has no effect.
 *
 * <p>Keys and values may be null. All optional multimap methods are supported, and all returned
 * views are modifiable.
 *
 * <p>This class is not threadsafe when any concurrent operations update the multimap. Concurrent
 * read operations will work correctly. To allow concurrent update operations, wrap your multimap
 * with a call to {@link Multimaps#synchronizedSetMultimap}.
 *
 * <p><b>Warning:</b> Do not modify either a key <i>or a value</i> of a {@code LinkedHashMultimap}
 * in a way that affects its {@link Object#equals} behavior. Undefined behavior and bugs will
 * result.
 *
 * <p>See the Guava User Guide article on <a href=
 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap"> {@code
 * Multimap}</a>.
 *
 * @author Jared Levy
 * @author Louis Wasserman
 * @since 2.0
 */
@GwtCompatible(serializable = true, emulated = true)
@ElementTypesAreNonnullByDefault
public final class LinkedHashMultimap<K extends @Nullable Object, V extends @Nullable Object>
        extends LinkedHashMultimapGwtSerializationDependencies<K, V>
{

    /**
     * Creates a new, empty {@code LinkedHashMultimap} with the default initial capacities.
     */
    public static <K extends @Nullable Object, V extends @Nullable Object>
    LinkedHashMultimap<K, V> create()
    {
        return new LinkedHashMultimap<>(DEFAULT_KEY_CAPACITY, DEFAULT_VALUE_SET_CAPACITY);
    }

    /**
     * Constructs an empty {@code LinkedHashMultimap} with enough capacity to hold the specified
     * numbers of keys and values without rehashing.
     *
     * @param expectedKeys         the expected number of distinct keys
     * @param expectedValuesPerKey the expected average number of values per key
     * @throws IllegalArgumentException if {@code expectedKeys} or {@code expectedValuesPerKey} is
     *                                  negative
     */
    public static <K extends @Nullable Object, V extends @Nullable Object>
    LinkedHashMultimap<K, V> create(int expectedKeys, int expectedValuesPerKey)
    {
        return new LinkedHashMultimap<>(
                Maps.capacity(expectedKeys), Maps.capacity(expectedValuesPerKey));
    }

    /**
     * Constructs a {@code LinkedHashMultimap} with the same mappings as the specified multimap. If a
     * key-value mapping appears multiple times in the input multimap, it only appears once in the
     * constructed multimap. The new multimap has the same {@link Multimap#entries()} iteration order
     * as the input multimap, except for excluding duplicate mappings.
     *
     * @param multimap the multimap whose contents are copied to this multimap
     */
    public static <K extends @Nullable Object, V extends @Nullable Object>
    LinkedHashMultimap<K, V> create(Multimap<? extends K, ? extends V> multimap)
    {
        LinkedHashMultimap<K, V> result = create(multimap.keySet().size(), DEFAULT_VALUE_SET_CAPACITY);
        result.putAll(multimap);
        return result;
    }

    private interface ValueSetLink<K extends @Nullable Object, V extends @Nullable Object>
    {
        ValueSetLink<K, V> getPredecessorInValueSet();

        ValueSetLink<K, V> getSuccessorInValueSet();

        void setPredecessorInValueSet(ValueSetLink<K, V> entry);

        void setSuccessorInValueSet(ValueSetLink<K, V> entry);
    }

    private static <K extends @Nullable Object, V extends @Nullable Object> void succeedsInValueSet(
            ValueSetLink<K, V> pred, ValueSetLink<K, V> succ)
    {
        pred.setSuccessorInValueSet(succ);
        succ.setPredecessorInValueSet(pred);
    }

    private static <K extends @Nullable Object, V extends @Nullable Object> void succeedsInMultimap(
            ValueEntry<K, V> pred, ValueEntry<K, V> succ)
    {
        pred.setSuccessorInMultimap(succ);
        succ.setPredecessorInMultimap(pred);
    }

    private static <K extends @Nullable Object, V extends @Nullable Object> void deleteFromValueSet(
            ValueSetLink<K, V> entry)
    {
        succeedsInValueSet(entry.getPredecessorInValueSet(), entry.getSuccessorInValueSet());
    }

    private static <K extends @Nullable Object, V extends @Nullable Object> void deleteFromMultimap(
            ValueEntry<K, V> entry)
    {
        succeedsInMultimap(entry.getPredecessorInMultimap(), entry.getSuccessorInMultimap());
    }

    /**
     * LinkedHashMultimap entries are in no less than three coexisting linked lists: a bucket in the
     * hash table for a {@code Set<V>} associated with a key, the linked list of insertion-ordered
     * entries in that {@code Set<V>}, and the linked list of entries in the LinkedHashMultimap as a
     * whole.
     */
    @VisibleForTesting
    static final class ValueEntry<K extends @Nullable Object, V extends @Nullable Object>
            extends ImmutableEntry<K, V> implements ValueSetLink<K, V>
    {
        final int smearedValueHash;

        @CheckForNull
        ValueEntry<K, V> nextInValueBucket;
        /*
         * The *InValueSet and *InMultimap fields below are null after construction, but we almost
         * always call succeedsIn*() to initialize them immediately thereafter.
         *
         * The exception is the *InValueSet fields of multimapHeaderEntry, which are never set. (That
         * works out fine as long as we continue to be careful not to try delete them or iterate past
         * them.)
         *
         * We could consider "lying" and omitting @CheckNotNull from all these fields. Normally, I'm not
         * a fan of that: What if we someday implement (presumably to be enabled during tests only)
         * bytecode rewriting that checks for any null value that passes through an API with a
         * known-non-null type? But that particular problem might not arise here, since we're not
         * actually reading from the fields in any case in which they might be null (as proven by the
         * requireNonNull checks below). Plus, we're *already* lying here, since newHeader passes a null
         * key and value, which we pass to the superconstructor, even though the key and value type for
         * a given entry might not include null. The right fix for the header problems is probably to
         * define a separate MultimapLink interface with a separate "header" implementation, which
         * hopefully could avoid implementing Entry or ValueSetLink at all. (But note that that approach
         * requires us to define extra classes -- unfortunate under Android.) *Then* we could consider
         * lying about the fields below on the grounds that we always initialize them just after the
         * constructor -- an example of the kind of lying that our hypotheticaly bytecode rewriter would
         * already have to deal with, thanks to DI frameworks that perform field and method injection,
         * frameworks like Android that define post-construct hooks like Activity.onCreate, etc.
         */

        @CheckForNull
        ValueSetLink<K, V> predecessorInValueSet;
        @CheckForNull
        ValueSetLink<K, V> successorInValueSet;

        @CheckForNull
        ValueEntry<K, V> predecessorInMultimap;
        @CheckForNull
        ValueEntry<K, V> successorInMultimap;

        ValueEntry(
                @ParametricNullness K key,
                @ParametricNullness V value,
                int smearedValueHash,
                @CheckForNull ValueEntry<K, V> nextInValueBucket)
        {
            super(key, value);
            this.smearedValueHash = smearedValueHash;
            this.nextInValueBucket = nextInValueBucket;
        }

        @SuppressWarnings("nullness") // see the comment on the class fields, especially about newHeader
        static <K extends @Nullable Object, V extends @Nullable Object> ValueEntry<K, V> newHeader()
        {
            return new ValueEntry<>(null, null, 0, null);
        }

        boolean matchesValue(@CheckForNull Object v, int smearedVHash)
        {
            return smearedValueHash == smearedVHash && Objects.equal(getValue(), v);
        }

        @Override
        public ValueSetLink<K, V> getPredecessorInValueSet()
        {
            return requireNonNull(predecessorInValueSet); // see the comment on the class fields
        }

        @Override
        public ValueSetLink<K, V> getSuccessorInValueSet()
        {
            return requireNonNull(successorInValueSet); // see the comment on the class fields
        }

        @Override
        public void setPredecessorInValueSet(ValueSetLink<K, V> entry)
        {
            predecessorInValueSet = entry;
        }

        @Override
        public void setSuccessorInValueSet(ValueSetLink<K, V> entry)
        {
            successorInValueSet = entry;
        }

        public ValueEntry<K, V> getPredecessorInMultimap()
        {
            return requireNonNull(predecessorInMultimap); // see the comment on the class fields
        }

        public ValueEntry<K, V> getSuccessorInMultimap()
        {
            return requireNonNull(successorInMultimap); // see the comment on the class fields
        }

        public void setSuccessorInMultimap(ValueEntry<K, V> multimapSuccessor)
        {
            this.successorInMultimap = multimapSuccessor;
        }

        public void setPredecessorInMultimap(ValueEntry<K, V> multimapPredecessor)
        {
            this.predecessorInMultimap = multimapPredecessor;
        }
    }

    private static final int DEFAULT_KEY_CAPACITY = 16;
    private static final int DEFAULT_VALUE_SET_CAPACITY = 2;
    @VisibleForTesting
    static final double VALUE_SET_LOAD_FACTOR = 1.0;

    @VisibleForTesting
    transient int valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
    private transient ValueEntry<K, V> multimapHeaderEntry;

    private LinkedHashMultimap(int keyCapacity, int valueSetCapacity)
    {
        super(Platform.<K, Collection<V>>newLinkedHashMapWithExpectedSize(keyCapacity));
        checkNonnegative(valueSetCapacity, "expectedValuesPerKey");

        this.valueSetCapacity = valueSetCapacity;
        this.multimapHeaderEntry = ValueEntry.newHeader();
        succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
    }

    /**
     * {@inheritDoc}
     *
     * <p>Creates an empty {@code LinkedHashSet} for a collection of values for one key.
     *
     * @return a new {@code LinkedHashSet} containing a collection of values for one key
     */
    @Override
    Set<V> createCollection()
    {
        return Platform.newLinkedHashSetWithExpectedSize(valueSetCapacity);
    }

    /**
     * {@inheritDoc}
     *
     * <p>Creates a decorated insertion-ordered set that also keeps track of the order in which
     * key-value pairs are added to the multimap.
     *
     * @param key key to associate with values in the collection
     * @return a new decorated set containing a collection of values for one key
     */
    @Override
    Collection<V> createCollection(@ParametricNullness K key)
    {
        return new ValueSet(key, valueSetCapacity);
    }

    /**
     * {@inheritDoc}
     *
     * <p>If {@code values} is not empty and the multimap already contains a mapping for {@code key},
     * the {@code keySet()} ordering is unchanged. However, the provided values always come last in
     * the {@link #entries()} and {@link #values()} iteration orderings.
     */
    @CanIgnoreReturnValue
    @Override
    public Set<V> replaceValues(@ParametricNullness K key, Iterable<? extends V> values)
    {
        return super.replaceValues(key, values);
    }

    /**
     * Returns a set of all key-value pairs. Changes to the returned set will update the underlying
     * multimap, and vice versa. The entries set does not support the {@code add} or {@code addAll}
     * operations.
     *
     * <p>The iterator generated by the returned set traverses the entries in the order they were
     * added to the multimap.
     *
     * <p>Each entry is an immutable snapshot of a key-value mapping in the multimap, taken at the
     * time the entry is returned by a method call to the collection or its iterator.
     */
    @Override
    public Set<Entry<K, V>> entries()
    {
        return super.entries();
    }

    /**
     * Returns a view collection of all <i>distinct</i> keys contained in this multimap. Note that the
     * key set contains a key if and only if this multimap maps that key to at least one value.
     *
     * <p>The iterator generated by the returned set traverses the keys in the order they were first
     * added to the multimap.
     *
     * <p>Changes to the returned set will update the underlying multimap, and vice versa. However,
     * <i>adding</i> to the returned set is not possible.
     */
    @Override
    public Set<K> keySet()
    {
        return super.keySet();
    }

    /**
     * Returns a collection of all values in the multimap. Changes to the returned collection will
     * update the underlying multimap, and vice versa.
     *
     * <p>The iterator generated by the returned collection traverses the values in the order they
     * were added to the multimap.
     */
    @Override
    public Collection<V> values()
    {
        return super.values();
    }

    @VisibleForTesting
    @WeakOuter
    final class ValueSet extends Sets.ImprovedAbstractSet<V> implements ValueSetLink<K, V>
    {
        /*
         * We currently use a fixed load factor of 1.0, a bit higher than normal to reduce memory
         * consumption.
         */

        @ParametricNullness
        private final K key;
        @VisibleForTesting
        @Nullable
        ValueEntry<K, V>[] hashTable;
        private int size = 0;
        private int modCount = 0;

        // We use the set object itself as the end of the linked list, avoiding an unnecessary
        // entry object per key.
        private ValueSetLink<K, V> firstEntry;
        private ValueSetLink<K, V> lastEntry;

        ValueSet(@ParametricNullness K key, int expectedValues)
        {
            this.key = key;
            this.firstEntry = this;
            this.lastEntry = this;
            // Round expected values up to a power of 2 to get the table size.
            int tableSize = Hashing.closedTableSize(expectedValues, VALUE_SET_LOAD_FACTOR);

            @SuppressWarnings({"rawtypes", "unchecked"})
            @Nullable
            ValueEntry<K, V>[] hashTable = new @Nullable ValueEntry[tableSize];
            this.hashTable = hashTable;
        }

        private int mask()
        {
            return hashTable.length - 1;
        }

        @Override
        public ValueSetLink<K, V> getPredecessorInValueSet()
        {
            return lastEntry;
        }

        @Override
        public ValueSetLink<K, V> getSuccessorInValueSet()
        {
            return firstEntry;
        }

        @Override
        public void setPredecessorInValueSet(ValueSetLink<K, V> entry)
        {
            lastEntry = entry;
        }

        @Override
        public void setSuccessorInValueSet(ValueSetLink<K, V> entry)
        {
            firstEntry = entry;
        }

        @Override
        public Iterator<V> iterator()
        {
            return new Iterator<V>()
            {
                ValueSetLink<K, V> nextEntry = firstEntry;
                @CheckForNull
                ValueEntry<K, V> toRemove;
                int expectedModCount = modCount;

                private void checkForComodification()
                {
                    if (modCount != expectedModCount)
                    {
                        throw new ConcurrentModificationException();
                    }
                }

                @Override
                public boolean hasNext()
                {
                    checkForComodification();
                    return nextEntry != ValueSet.this;
                }

                @Override
                @ParametricNullness
                public V next()
                {
                    if (!hasNext())
                    {
                        throw new NoSuchElementException();
                    }
                    ValueEntry<K, V> entry = (ValueEntry<K, V>) nextEntry;
                    V result = entry.getValue();
                    toRemove = entry;
                    nextEntry = entry.getSuccessorInValueSet();
                    return result;
                }

                @Override
                public void remove()
                {
                    checkForComodification();
                    checkState(toRemove != null, "no calls to next() since the last call to remove()");
                    ValueSet.this.remove(toRemove.getValue());
                    expectedModCount = modCount;
                    toRemove = null;
                }
            };
        }

        @Override
        public int size()
        {
            return size;
        }

        @Override
        public boolean contains(@CheckForNull Object o)
        {
            int smearedHash = Hashing.smearedHash(o);
            for (ValueEntry<K, V> entry = hashTable[smearedHash & mask()];
                 entry != null;
                 entry = entry.nextInValueBucket)
            {
                if (entry.matchesValue(o, smearedHash))
                {
                    return true;
                }
            }
            return false;
        }

        @Override
        public boolean add(@ParametricNullness V value)
        {
            int smearedHash = Hashing.smearedHash(value);
            int bucket = smearedHash & mask();
            ValueEntry<K, V> rowHead = hashTable[bucket];
            for (ValueEntry<K, V> entry = rowHead; entry != null; entry = entry.nextInValueBucket)
            {
                if (entry.matchesValue(value, smearedHash))
                {
                    return false;
                }
            }

            ValueEntry<K, V> newEntry = new ValueEntry<>(key, value, smearedHash, rowHead);
            succeedsInValueSet(lastEntry, newEntry);
            succeedsInValueSet(newEntry, this);
            succeedsInMultimap(multimapHeaderEntry.getPredecessorInMultimap(), newEntry);
            succeedsInMultimap(newEntry, multimapHeaderEntry);
            hashTable[bucket] = newEntry;
            size++;
            modCount++;
            rehashIfNecessary();
            return true;
        }

        private void rehashIfNecessary()
        {
            if (Hashing.needsResizing(size, hashTable.length, VALUE_SET_LOAD_FACTOR))
            {
                @SuppressWarnings("unchecked")
                ValueEntry<K, V>[] hashTable = new ValueEntry[this.hashTable.length * 2];
                this.hashTable = hashTable;
                int mask = hashTable.length - 1;
                for (ValueSetLink<K, V> entry = firstEntry;
                     entry != this;
                     entry = entry.getSuccessorInValueSet())
                {
                    ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
                    int bucket = valueEntry.smearedValueHash & mask;
                    valueEntry.nextInValueBucket = hashTable[bucket];
                    hashTable[bucket] = valueEntry;
                }
            }
        }

        @CanIgnoreReturnValue
        @Override
        public boolean remove(@CheckForNull Object o)
        {
            int smearedHash = Hashing.smearedHash(o);
            int bucket = smearedHash & mask();
            ValueEntry<K, V> prev = null;
            for (ValueEntry<K, V> entry = hashTable[bucket];
                 entry != null;
                 prev = entry, entry = entry.nextInValueBucket)
            {
                if (entry.matchesValue(o, smearedHash))
                {
                    if (prev == null)
                    {
                        // first entry in the bucket
                        hashTable[bucket] = entry.nextInValueBucket;
                    }
                    else
                    {
                        prev.nextInValueBucket = entry.nextInValueBucket;
                    }
                    deleteFromValueSet(entry);
                    deleteFromMultimap(entry);
                    size--;
                    modCount++;
                    return true;
                }
            }
            return false;
        }

        @Override
        public void clear()
        {
            Arrays.fill(hashTable, null);
            size = 0;
            for (ValueSetLink<K, V> entry = firstEntry;
                 entry != this;
                 entry = entry.getSuccessorInValueSet())
            {
                ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
                deleteFromMultimap(valueEntry);
            }
            succeedsInValueSet(this, this);
            modCount++;
        }
    }

    @Override
    Iterator<Entry<K, V>> entryIterator()
    {
        return new Iterator<Entry<K, V>>()
        {
            ValueEntry<K, V> nextEntry = multimapHeaderEntry.getSuccessorInMultimap();
            @CheckForNull
            ValueEntry<K, V> toRemove;

            @Override
            public boolean hasNext()
            {
                return nextEntry != multimapHeaderEntry;
            }

            @Override
            public Entry<K, V> next()
            {
                if (!hasNext())
                {
                    throw new NoSuchElementException();
                }
                ValueEntry<K, V> result = nextEntry;
                toRemove = result;
                nextEntry = nextEntry.getSuccessorInMultimap();
                return result;
            }

            @Override
            public void remove()
            {
                checkState(toRemove != null, "no calls to next() since the last call to remove()");
                LinkedHashMultimap.this.remove(toRemove.getKey(), toRemove.getValue());
                toRemove = null;
            }
        };
    }

    @Override
    Iterator<V> valueIterator()
    {
        return Maps.valueIterator(entryIterator());
    }

    @Override
    public void clear()
    {
        super.clear();
        succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
    }

    /**
     * @serialData the expected values per key, the number of distinct keys, the number of entries,
     * and the entries in order
     */
    @GwtIncompatible // java.io.ObjectOutputStream
    private void writeObject(ObjectOutputStream stream) throws IOException
    {
        stream.defaultWriteObject();
        stream.writeInt(keySet().size());
        for (K key : keySet())
        {
            stream.writeObject(key);
        }
        stream.writeInt(size());
        for (Entry<K, V> entry : entries())
        {
            stream.writeObject(entry.getKey());
            stream.writeObject(entry.getValue());
        }
    }

    @GwtIncompatible // java.io.ObjectInputStream
    private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException
    {
        stream.defaultReadObject();
        multimapHeaderEntry = ValueEntry.newHeader();
        succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
        valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
        int distinctKeys = stream.readInt();
        Map<K, Collection<V>> map = Platform.newLinkedHashMapWithExpectedSize(12);
        for (int i = 0; i < distinctKeys; i++)
        {
            @SuppressWarnings("unchecked")
            K key = (K) stream.readObject();
            map.put(key, createCollection(key));
        }
        int entries = stream.readInt();
        for (int i = 0; i < entries; i++)
        {
            @SuppressWarnings("unchecked")
            K key = (K) stream.readObject();
            @SuppressWarnings("unchecked")
            V value = (V) stream.readObject();
            /*
             * requireNonNull is safe for a properly serialized multimap: We've already inserted a
             * collection for each key that we expect.
             */
            requireNonNull(map.get(key)).add(value);
        }
        setMap(map);
    }

    @GwtIncompatible // java serialization not supported
    private static final long serialVersionUID = 1;
}
